// dp[-1][k][0] = 0
// 解释：因为 i 是从 0 开始的，所以 i = -1 意味着还没有开始，这时候的利润当然是 0 。
// dp[-1][k][1] = -infinity
// 解释：还没开始的时候，是不可能持有股票的，用负无穷表示这种不可能。
// dp[i][0][0] = 0
// 解释：因为 k 是从 1 开始的，所以 k = 0 意味着根本不允许交易，这时候利润当然是 0 。
// dp[i][0][1] = -infinity
// 解释：不允许交易的情况下，是不可能持有股票的，用负无穷表示这种不可能。


// dp[-1][k][0] = 0
// 解释：因为 i 是从 0 开始的，所以 i = -1 意味着还没有开始，这时候的利润当然是 0 。
// dp[-1][k][1] = -infinity
// 解释：还没开始的时候，是不可能持有股票的，用负无穷表示这种不可能。
// dp[i][0][0] = 0
// 解释：因为 k 是从 1 开始的，所以 k = 0 意味着根本不允许交易，这时候利润当然是 0 。
// dp[i][0][1] = -infinity
// 解释：不允许交易的情况下，是不可能持有股票的，用负无穷表示这种不可能。


// base case：
// dp[-1][k][0] = dp[i][0][0] = 0
// dp[-1][k][1] = dp[i][0][1] = -infinity
//
// 状态转移方程：
// dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
// dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])


// 第一题 k = 1
var maxProfit = function (prices) {
    let n = prices.length;
    if (n <= 1) {
        return 0;
    }
    let dp = new Array(n);

    dp.fill([0, 0], 0, n)
    console.log(dp)

    // base case
    // 解释：
    //   dp[i][0]
    // = max(dp[-1][0], dp[-1][1] + prices[i])
    // = max(0, -infinity + prices[i]) = 0
    dp[0][0] = 0;

    // 解释：
    //   dp[i][1]
    // = max(dp[-1][1], dp[-1][0] - prices[i])
    // = max(-infinity, 0 - prices[i])
    // = -prices[i]
    dp[0][1] = -prices[0];

    // 状态转移
    for (let i = 1; i < n; i++) {
        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
        dp[i][1] = Math.max(dp[i - 1][1], -prices[i])
    }
    console.log(dp)
    return dp[n - 1][0]
};

// maxProfit([7, 1, 5, 3, 6, 4])
var maxProfit = function (prices) {
    let n = prices.length;

    // base case
    let dp_i_0 = 0, dp_i_1 = -prices[0];

    for (let i = 1; i < n; i++) {
        // dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
        dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);

        // dp[i][1] = max(dp[i-1][1], -prices[i])
        dp_i_1 = Math.max(dp_i_1, -prices[i]);
    }
    return dp_i_0;
}

// 第二题
/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
    let n = prices.length;
    let dp = new Array(n);
    dp.fill([0, 0], 0, n)

    dp[0][0] = 0;
    dp[0][1] = -prices[0];

    for (let i = 0; i < n; i++) {
        dp[i][0] = Math.max(
            dp[i - 1][0],
            dp[i - 1][1] + prices[i]
        )
        dp[i][1] = Math.max(
            dp[i - 1][1],
            dp[i - 1][0] - prices[i]
        )
    }
    return dp[n - 1][0]
};


/**
 * @param {number} k
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (k, prices) {
    let n = prices.length;

    // base case
    let dp_i_0 = 0, dp_i_1 = -prices[0];

    for (let i = 0; i < n; i++) {
        // dp[i][0] = Math.max(
        //             dp[i - 1][0],
        //             dp[i - 1][1] + prices[i]
        //         )
        dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);

        //  dp[i][1] = Math.max(
        //             dp[i - 1][1],
        //             dp[i - 1][0] - prices[i]
        //         )
        dp_i_1 = Math.max(dp_i_1, dp_i_0 - prices[i])
    }

    return dp_i_0;
};


// 第三题
/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
    let n = prices.length;

    if (n < 2) {
        return 0;
    }
    if (n === 2) {
        return Math.max(prices[1] - prices[0], 0)
    }
    let dp = new Array(n);
    for (let i = 0; i < n; i++) {
        dp[i] = [0, 0]
    }
    // dp.fill([0,0], 0, n)


    // base case
    // dp[0][0] = 0;
    dp[0][1] = -prices[0];
    dp[1][0] = Math.max(
        dp[0][0],
        dp[0][1] + prices[1]
    )
    dp[1][1] = Math.max(
        dp[0][1],
        dp[0][0] - prices[1]
    );
    console.log(dp)

    // 状态转移
    for (let i = 2; i < n; i++) {
        dp[i][0] = Math.max(
            dp[i - 1][0],
            dp[i - 1][1] + prices[i]
        )
        dp[i][1] = Math.max(
            dp[i - 1][1],
            dp[i - 2][0] - prices[i]   // 买被限制在卖一天后了
        )
    }
    console.log(dp)

    return dp[n - 1][0];
};

var maxProfit = function (prices) {
    let n = prices.length;
    let dp_i_0 = 0;
    let dp_i_1 = -Infinity;  // 还未买入
    let dp_pre_0 = 0;  // 代表 dp[i-2][0]

    for (let i = 0; i < n; i++) {
        let temp = dp_i_0;
        dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
        dp_i_1 = Math.max(dp_i_1, dp_pre_0 - prices[i]);
        dp_pre_0 = temp;
    }
    return dp_i_0;
};

// 第四题
/**
 * @param {number[]} prices
 * @param {number} fee
 * @return {number}
 */
var maxProfit = function (prices, fee) {
    let n = prices.length;
    let dp = new Array(n);
    for (let i = 0; i < n; i++) {
        dp[i] = [0, 0]
    }


    // base case
    // dp[0][0] = 0;
    dp[0][1] = -prices[0] - fee;

    // 状态转移
    for (let i = 1; i < n; i++) {
        dp[i][0] = Math.max(
            dp[i - 1][0],
            dp[i - 1][1] + prices[i]
        )
        dp[i][1] = Math.max(
            dp[i - 1][1],
            dp[i - 1][0] - prices[i] - fee  // 相当于买入股票的价格升高了
        )
    }

    return dp[n - 1][0];
};


var maxProfit = function (prices, fee) {
    let n = prices.length;

    // base case
    let dp_i_0 = 0, dp_i_1 = -prices[0] - fee;

    for (let i = 0; i < n; i++) {
        dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
        dp_i_1 = Math.max(dp_i_1, dp_i_0 - prices[i] - fee)
    }

    return dp_i_0;
};


// 第五题k=2
/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
    let n = prices.length;
    let max_k = 2;

    // dp[n][max_k + 1][2]
    // 把dp最后一个维度拆成两个数组
    let dp_unrest = new Array(n);  // 相当于0的情况
    let dp_rest = new Array(n); // 相当于1的情况

    for (let i = 0; i < n; i++) {
        dp_rest[i] = new Array(max_k + 1);
        dp_unrest[i] = new Array(max_k + 1);
    }

    // base case
    dp_unrest[0][0] = 0  // dp[0][k][0] = 0
    dp_rest[0][0] = -Infinity;  // dp[][][]
};


var maxProfit = function (prices) {
    let n = prices.length;
    let max_k = 2;

    // dp[n][max_k + 1][2]
    // 把dp最后一个维度拆成两个数组
    let dp = new Array(n);  // 相当于0的情况

    for (let i = 0; i < n; i++) {
        dp[i] = new Array(max_k + 1);
        for (let j = 0; j < max_k + 1; j++) {
            dp[i][j] = [0, 0]
        }
    }

    // base case


    // 状态转移
    for (let i = 0; i < n; i++) {
        for (let k = max_k; k >= 1; k--) {
            if (i - 1 === -1) {
                /* 处理 base case */
                dp[i][k][0] = Math.max(
                    0,       // 保持原样
                    -Infinity  // 卖出股票
                )
                dp[i][k][1] = Math.max(
                    -Infinity,       // 保持原样
                    dp[i - 1][k - 1][0] - prices[i]  // 买入股票
                )
                continue;
            }
            dp[i][k][0] = Math.max(
                dp[i - 1][k][0],       // 保持原样
                dp[i - 1][k][1] + prices[i]   // 卖出股票
            )
            dp[i][k][1] = Math.max(
                dp[i - 1][k][1],       // 保持原样
                dp[i - 1][k - 1][0] - prices[i]  // 买入股票
            )
        }
    }

    // 穷举了 n × max_k × 2 个状态，正确。
    return dp[n - 1][max_k][0];
};

var maxProfit_k_2 = function (prices) {
    let dp_i10 = 0, dp_i11 = -Number.MAX_VALUE;
    let dp_i20 = 0, dp_i21 = -Number.MAX_VALUE;
    for (let price of prices) {
        dp_i20 = Math.max(dp_i20, dp_i21 + price);
        dp_i21 = Math.max(dp_i21, dp_i10 - price);
        dp_i10 = Math.max(dp_i10, dp_i11 + price);
        dp_i11 = Math.max(dp_i11, -price);
    }
    return dp_i20;
}


// 第六题
var maxProfit = function (k, prices) {
    if (!prices.length) {
        return 0;
    }

    const n = prices.length;
    let max_k = Math.min(k, Math.floor(n / 2));

    for (let i = 0; i < n; i++) {
        dp[i] = new Array(max_k + 1);
        for (let j = 0; j < max_k + 1; j++) {
            dp[i][j] = [0, 0]
        }
    }

    dp[0][0][0] = 0;
    dp[0][0][1] = -prices[0];

    for (let i = 1; i <= k; ++i) {
        dp[0][i][1] = -Number.MAX_VALUE;
        dp[0][i][0] = -Number.MAX_VALUE;
    }

}